跟ChatGPT的對話是:我今天開始要it鐵人賽一天一題leetcode! 請幫我規劃今天要學習的是哪一題並請你化身我的leetcode家教,一步一步地帶我理解這一題的解法!
這題題目是要一個整數陣列 nums 和一個整數 target,要找出兩個不同索引 i、j,使得 nums[i] + nums[j] == target,所以例如nums = [2,7,11,15], target = 9 → 回傳 [0,1],因為 2 + 7 = 9
ChatGPT給的回答是: 方法一:暴力(最直觀)
思路:對每一個元素,試所有後面的元素,看是否和為 target。
步驟:雙層迴圈:i 從 0 到 n-1,j 從 i+1 到 n-1,檢查 nums[i] + nums[j]
首先,我們需要用 HashMap,這是一種「字典型」的資料結構,可以讓我們用「key → value」的方式快速存取資料。在這題裡,key 是數字(陣列裡的值),value 是它的索引。
import java.util.HashMap;
import java.util.Map;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return null; // 題目保證有解,其實這行不會執行
}
}
定義了一個 twoSum 函式,輸入是:
nums: 陣列(整數)
target: 目標數字
輸出是一個「陣列」(int[]),裡面放兩個索引。
建立一個空的 HashMap,名字叫 map。
它會存「數字 → 索引」。
例如:nums = [2,7,11],如果我把 2 存進去,就會變成 {2:0}(數字 2 在索引 0)。
用一個迴圈,從陣列的第一個元素跑到最後一個。
i 是索引,nums[i] 是值。
算出「補數」(complement)。
意思是:如果 nums[i] 已經拿了一個數,那麼我要找另一個數,讓兩個數加起來等於 target。
所以另一個數就是 target - nums[i]。
檢查 map 裡面有沒有存過「補數」。
map.containsKey(complement):如果補數已經在 map 裡了 → 太棒了,我找到答案了!
map.get(complement):拿到補數的索引。
i:是現在這個數的索引。
return new int[]{map.get(complement), i}; → 回傳一個陣列,兩個位置就是答案。
總結就是你就想像自己在逛超市,目標是花剛好 target 元買兩樣東西。
每看到一樣東西,就會想:
「如果我買了它,我還需要什麼補差價?」,然後你檢查購物車(map)裡有沒有那個補差價的東西。
有 → 配對成功,結帳!
沒有 → 先把這個東西放進購物車,等下一個商品來配對。